/*
* leetcode 394. 字符串解码
*
给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

示例 1：

输入：s = "3[a]2[bc]"
输出："aaabcbc"
* */
/* 栈+分类讨论
* */
import java.util.*;
class Solution {
    public String decodeString(String s) {
        int i=0,n=s.length();;
        char[] cs=s.toCharArray();
        Deque<Integer> num=new ArrayDeque<>();
        Deque<StringBuffer> letter=new ArrayDeque<>();
        letter.push(new StringBuffer());
        while(i<n){
            if(cs[i]>='0'&&cs[i]<='9'){
                int tmp=0;
                while(i<n&&cs[i]>='0'&&cs[i]<='9'){
                    tmp=tmp*10+(cs[i]-'0');
                    i++;
                }
                num.push(tmp);
            }else if(cs[i]=='['){
                i++;
                StringBuffer str=new StringBuffer();
                while(i<n&&cs[i]>='a'&&cs[i]<='z'){
                    str.append(cs[i]);
                    i++;
                }
                letter.push(str);
            }else if(cs[i]==']'){
                int cnt=num.pop();
                StringBuffer str=letter.pop();
                while(cnt-->0){
                    letter.peek().append(str);
                }
                i++;
            }else{
                StringBuffer str=new StringBuffer();
                while(i<n&&cs[i]>='a'&&cs[i]<='z'){
                    letter.peek().append(cs[i]);
                    i++;
                }
            }
        }
        return letter.pop().toString();
    }
}